package org.example.algorithm.dp;

public class UniquePathsSolution {

    public static void main(String[] args) {
        int m = 3;
        int n = 7;
        UniquePathsSolution solution = new UniquePathsSolution();
        int res = solution.uniquePaths(m, n);
        System.out.println(res);
    }

    //排列组合
    public int uniquePaths2(int m, int n) {
        int step = m - 1 + n - 1;
        int min = Math.min(m-1, n-1);
        long ans = 1;
        for (int i=0;i<min;i++) {
            ans = ans * (step - i) / (i + 1);
        }
        return Math.toIntExact(ans);
    }

    //dp[i][j] = dp[i-1][j] + dp[i][j-1]
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (i==0 || j==0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
